import java.util.ArrayList;
import java.util.List;

// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> averages = new ArrayList<>();
        if (root == null) {
            return averages;
        }
        List<List<Integer>> levelValues = new ArrayList<>();
        dfs(root, 0, levelValues);
        for (List<Integer> level : levelValues) {
            double sum = 0;
            for (int val : level) {
                sum += val;
            }
            averages.add(sum / level.size());
        }
        return averages;
    }

    public void dfs(TreeNode root, int level, List<List<Integer>> levelValues) {
        if (root == null) {
            return;
        }
        if (levelValues.size() <= level) {
            levelValues.add(new ArrayList<>());
        }
        levelValues.get(level).add(root.val);
        dfs(root.left, level + 1, levelValues);
        dfs(root.right, level + 1, levelValues);
    }

    public static void main(String[] args) {
        // 构建测试用例二叉树
        //       3
        //      / \
        //     9  20
        //       /  \
        //      15   7
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        Solution solution = new Solution();
        List<Double> averages = solution.averageOfLevels(root);

        // 输出结果
        System.out.println("每一层的平均值为: " + averages);
        // 预期输出: [3.0, 14.5, 11.0]
    }
}